import java.util.Arrays;

/**
 * @program: 20222.17 堆
 * @description:
 * @author: 李鑫月
 * @create: 2022-02-17 15:06
 **/
public class TestHeap {
    public int[] arr;
    public int usedSize;
    public TestHeap(int a){
        System.out.println("a");
    }
    public TestHeap(){
        arr=new int[10];
    }
    public void createHeap(int[] array){
        for(int i=0;i<array.length;i++){
            this.arr[i]=array[i];
            usedSize++;
        }
     int parrent=(usedSize-1-1)/2;
        for (; parrent >=0 ; parrent--) {
            shiftDwon(this.arr,usedSize,parrent);
        }

    }
    public void shiftDwon(int[] arr,int len,int parrent){
        int child=parrent*2+1;
        while (child<len){
            if(child+1<len && arr[child+1]>arr[child]){
                child++;
            }
            if(arr[child]>arr[parrent]){
                int tmp=arr[child];
                arr[child]=arr[parrent];
                arr[parrent]=tmp;
                parrent=child;
                child=2*parrent+1;
            }else {
                break;
            }
        }

    }
    public  void shiftUp(int child){
        int parrent=(child-1)/2;
        while(parrent>=0){
            if(arr[child]>arr[parrent]){
                int tmp=arr[child];
                arr[child]=arr[parrent];
                arr[parrent]=tmp;
                child=parrent;
                parrent=(child-1)/2;
            }else {
                break;
            }
        }

    }
    public void offer(int val){
        if(isfull()){
            arr=Arrays.copyOf(arr,2*arr.length);
        }
            arr[usedSize++]=val;

        shiftUp(usedSize-1);
    }
    public boolean isfull(){
        return this.usedSize==this.arr.length;
    }
    public int poll(){
        if(isEmpty()){
            throw new RuntimeException("优先级队列为空");
        }
        int tmp=arr[0];
        arr[0]=arr[usedSize-1];
        arr[usedSize-1]=tmp;
        usedSize--;
        shiftDwon(arr,usedSize,0);
        return tmp;
    }
    public boolean isEmpty(){
        return usedSize==0;
    }
    public void heapSort(){
        int end=usedSize-1;
        while(end>0){
            int tmp=arr[0];
            arr[0]=arr[end];
            arr[end]=tmp;
            shiftDwon(arr,end,0);
            end--;
        }

    }
}
